We are looking at worlds that are uncertain and involve time.

No, every world or environment involves time.

We're interested here in environments where the changes in the world are approximately

at the same time scale as our deliberation times.

That it actually matters what we do, that time matters, so that we actually have to

model it explicitly.

Remember, the basic idea is very simple.

We have a couple of random variables we're interested in, and we'll just index those

by a time structure.

Very simple.

The first thing you would have come up with.

The only thing that is slightly more interesting here is that you can take arbitrary time

structures, but we're not doing that.

We keep to the simple stuff.

We have these time structures and these random variables that are indexed by time, which

gives us all kinds of infinitudes or biggitudes, where we can have an unbounded number of dependencies

or so, because all of it is potentially infinite.

The first thing we do is we define all of that away by various assumptions.

We assume that our problems are stationary, which means we always have the same transition

model independent of time, and we assume Markov properties, which essentially bounds the number

of incoming influences at each node, influences from the past.

To be really on the safe side, we actually bound that number to be one.

There's a theory out there for two and three and n in general, but it's a little bit more

difficult, so we're not doing it here.

Under these assumptions, which are surprisingly realistic.

Normally all the assumptions we've done so far have been just ludicrous.

It's clear that there are almost no worlds where they really actually apply.

These are actually the Markov assumptions, cover a pretty broad case of interesting examples.

We are looking at, and that's what we did yesterday, we looked at a couple of inference

procedures.

Filtering or monitoring, which is updating our belief state, namely what are the possible

models and how likely are they in light of a sequence of evidences.

We have prediction, which is the same thing, creating or computing a belief space for future

events, not just for the current unseen event.

We looked at smoothing, which does the same thing for the past.

Finally, we looked at most likely explanation and looked at the Vita-Abhi algorithm that

actually gave us something there.

Just to remind you, what we're doing is essentially we're using our probabilistic machinery here

plus lots of conditional independence assumptions, which are the Markov assumptions, to get a

recursive algorithm for estimating state, for estimating the posterior probability distribution

of the random variables we're interested in.

The basic idea and simplification is that from this computation, we have this forward

message from one to t, which we pass on recursively.

That gives us an algorithm that's constant time and constant space for every update,

which is exactly what we want for our agent.

Of course, the thing you want to realize is that whenever there's a bold phase p here

and something like sums and multiplications and so on, we have huge multi-dimensional

sums of equations, which is something we're going to look at in these Markov chains.

But the upshot is we have a simple recursive or iterative algorithm that helps us a lot.

We looked at the umbrellas example, and we basically always had two movements here.